<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: Chapter 4</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: Chapter 4" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: Chapter 4" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="index.xhtml#Top" rel="prev" title="Top" />
<link href="4_002e1.xhtml#g_t4_002e1" rel="next" title="4.1" />
<link href="3_002e5.xhtml#g_t3_002e5_002e5" rel="prev" title="3.5.5" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="Chapter-4"></a>
<nav class="header">
<p>
Next: <a href="4_002e1.xhtml#g_t4_002e1" accesskey="n" rel="next">4.1</a>, Prev: <a href="3_002e5.xhtml#g_t3_002e5" accesskey="p" rel="prev">3.5</a>, Up: <a href="index.xhtml#Top" accesskey="u" rel="prev">Top</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="Metalinguistic-Abstraction"></a>
<h2 class="chapter"><span class="chapnum">4</span><span class="chaptitle">Metalinguistic Abstraction</span></h2>

<blockquote>
<p>… It’s in words that the magic is—Abracadabra, Open Sesame, and the
rest—but the magic words in one story aren’t magical in the next.  The real
magic is to understand which words work, and when, and for what; the trick is
to learn the trick.
</p>
<p>… And those words are made from the letters of our alphabet: a
couple-dozen squiggles we can draw with the pen.  This is the key!  And the
treasure, too, if we can only get our hands on it!  It’s as if—as if the key
to the treasure <em>is</em> the treasure!
</p>
<p>—John Barth, <cite>Chimera</cite>
</p></blockquote>


<p>In our study of program design, we have seen that expert programmers control
the complexity of their designs with the same general techniques used by
designers of all complex systems.  They combine primitive elements to form
compound objects, they abstract compound objects to form higher-level building
blocks, and they preserve modularity by adopting appropriate large-scale views
of system structure.  In illustrating these techniques, we have used Lisp as a
language for describing processes and for constructing computational data
objects and processes to model complex phenomena in the real world.  However,
as we confront increasingly complex problems, we will find that Lisp, or indeed
any fixed programming language, is not sufficient for our needs.  We must
constantly turn to new languages in order to express our ideas more
effectively.  Establishing new languages is a powerful strategy for controlling
complexity in engineering design; we can often enhance our ability to deal with
a complex problem by adopting a new language that enables us to describe (and
hence to think about) the problem in a different way, using primitives, means
of combination, and means of abstraction that are particularly well suited to
the problem at hand.<a class="footnote_link" id="DOCF205" href="#FOOT205"><sup>205</sup></a>
</p>
<p>Programming is endowed with a multitude of languages.  There are physical
languages, such as the machine languages for particular computers.  These
languages are concerned with the representation of data and control in terms of
individual bits of storage and primitive machine instructions.  The
machine-language programmer is concerned with using the given hardware to erect
systems and utilities for the efficient implementation of resource-limited
computations.  High-level languages, erected on a machine-language substrate,
hide concerns about the representation of data as collections of bits and the
representation of programs as sequences of primitive instructions.  These
languages have means of combination and abstraction, such as procedure
definition, that are appropriate to the larger-scale organization of systems.
</p>
<a id="index-Metalinguistic-abstraction"></a>
<p><em>Metalinguistic abstraction</em>—establishing new languages—plays an
important role in all branches of engineering design.  It is particularly
important to computer programming, because in programming not only can we
formulate new languages but we can also implement these languages by
constructing evaluators.  An <a id="index-evaluator"></a>
<em>evaluator</em> (or <a id="index-interpreter-1"></a>
<em>interpreter</em>) for
a programming language is a procedure that, when applied to an expression of
the language, performs the actions required to evaluate that expression.
</p>
<p>It is no exaggeration to regard this as the most fundamental idea in
programming:
</p>
<blockquote>
<p>The evaluator, which determines the meaning of expressions in a programming
language, is just another program.
</p></blockquote>

<p>To appreciate this point is to change our images of ourselves as programmers.
We come to see ourselves as designers of languages, rather than only users of
languages designed by others.
</p>
<p>In fact, we can regard almost any program as the evaluator for some language.
For instance, the polynomial manipulation system of <a href="2_002e5.xhtml#g_t2_002e5_002e3">2.5.3</a>
embodies the rules of polynomial arithmetic and implements them in terms of
operations on list-structured data.  If we augment this system with procedures
to read and print polynomial expressions, we have the core of a special-purpose
language for dealing with problems in symbolic mathematics.  The digital-logic
simulator of <a href="3_002e3.xhtml#g_t3_002e3_002e4">3.3.4</a> and the constraint propagator of 
<a href="3_002e3.xhtml#g_t3_002e3_002e5">3.3.5</a> are legitimate languages in their own right, each with its own
primitives, means of combination, and means of abstraction.  Seen from this
perspective, the technology for coping with large-scale computer systems merges
with the technology for building new computer languages, and computer science
itself becomes no more (and no less) than the discipline of constructing
appropriate descriptive languages.
</p>
<p>We now embark on a tour of the technology by which languages are established in
terms of other languages.  In this chapter we shall use Lisp as a base,
implementing evaluators as Lisp procedures.  Lisp is particularly well suited
to this task, because of its ability to represent and manipulate symbolic
expressions.  We will take the first step in understanding how languages are
implemented by building an evaluator for Lisp itself.  The language implemented
by our evaluator will be a subset of the Scheme dialect of Lisp that we use in
this book.  Although the evaluator described in this chapter is written for a
particular dialect of Lisp, it contains the essential structure of an evaluator
for any expression-oriented language designed for writing programs for a
sequential machine.  (In fact, most language processors contain, deep within
them, a little “Lisp” evaluator.)  The evaluator has been simplified for the
purposes of illustration and discussion, and some features have been left out
that would be important to include in a production-quality Lisp system.
Nevertheless, this simple evaluator is adequate to execute most of the programs
in this book.<a class="footnote_link" id="DOCF206" href="#FOOT206"><sup>206</sup></a>
</p>
<p>An important advantage of making the evaluator accessible as a Lisp program is
that we can implement alternative evaluation rules by describing these as
modifications to the evaluator program.  One place where we can use this power
to good effect is to gain extra control over the ways in which computational
models embody the notion of time, which was so central to the discussion in
<a href="Chapter-3.xhtml#Chapter-3">Chapter 3</a>.  There, we mitigated some of the complexities of state and
assignment by using streams to decouple the representation of time in the world
from time in the computer.  Our stream programs, however, were sometimes
cumbersome, because they were constrained by the applicative-order evaluation
of Scheme.  In <a href="4_002e2.xhtml#g_t4_002e2">4.2</a>, we’ll change the underlying language to
provide for a more elegant approach, by modifying the evaluator to provide for
<a id="index-normal_002dorder-evaluation-1"></a>
<em>normal-order evaluation</em>.
</p>
<p>Section <a href="4_002e3.xhtml#g_t4_002e3">4.3</a> implements a more ambitious linguistic change, whereby
expressions have many values, rather than just a single value.  In this
language of <a id="index-nondeterministic-computing"></a>
<em>nondeterministic computing</em>, it is natural to express
processes that generate all possible values for expressions and then search for
those values that satisfy certain constraints.  In terms of models of
computation and time, this is like having time branch into a set of “possible
futures” and then searching for appropriate time lines.  With our
nondeterministic evaluator, keeping track of multiple values and performing
searches are handled automatically by the underlying mechanism of the language.
</p>
<p>In <a href="4_002e4.xhtml#g_t4_002e4">4.4</a> we implement a <a id="index-logic_002dprogramming"></a>
<em>logic-programming</em> language in
which knowledge is expressed in terms of relations, rather than in terms of
computations with inputs and outputs.  Even though this makes the language
drastically different from Lisp, or indeed from any conventional language, we
will see that the logic-programming evaluator shares the essential structure of
the Lisp evaluator.
</p>

<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT205"><p><a class="footnote_backlink" href="#DOCF205"><sup>205</sup></a>
The same idea is pervasive throughout all of
engineering.  For example, electrical engineers use many different languages
for describing circuits.  Two of these are the language of electrical
<a id="index-networks"></a>
<em>networks</em> and the language of electrical <a id="index-systems"></a>
<em>systems</em>.  The
network language emphasizes the physical modeling of devices in terms of
discrete electrical elements.  The primitive objects of the network language
are primitive electrical components such as resistors, capacitors, inductors,
and transistors, which are characterized in terms of physical variables called
voltage and current.  When describing circuits in the network language, the
engineer is concerned with the physical characteristics of a design.  In
contrast, the primitive objects of the system language are signal-processing
modules such as filters and amplifiers.  Only the functional behavior of the
modules is relevant, and signals are manipulated without concern for their
physical realization as voltages and currents.  The system language is erected
on the network language, in the sense that the elements of signal-processing
systems are constructed from electrical networks.  Here, however, the concerns
are with the large-scale organization of electrical devices to solve a given
application problem; the physical feasibility of the parts is assumed.  This
layered collection of languages is another example of the stratified design
technique illustrated by the picture language of <a href="2_002e2.xhtml#g_t2_002e2_002e4">2.2.4</a>.</p>
</div>
<div id="FOOT206"><p><a class="footnote_backlink" href="#DOCF206"><sup>206</sup></a>
The most important features that our evaluator leaves
out are mechanisms for handling errors and supporting debugging.  For a more
extensive discussion of evaluators, see <a href="References.xhtml#Friedman-et-al_002e-1992">Friedman et al. 1992</a>, which
gives an exposition of programming languages that proceeds via a sequence of
evaluators written in Scheme.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="4_002e1.xhtml#g_t4_002e1" accesskey="n" rel="next">4.1</a>, Prev: <a href="3_002e5.xhtml#g_t3_002e5" accesskey="p" rel="prev">3.5</a>, Up: <a href="index.xhtml#Top" accesskey="u" rel="prev">Top</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>